package lib

import (
	"strconv"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         902,
		Discription: "和<=n的数位组合个数",
		Level:       3,
		Labels: map[string]int{
			"动态规划":   1,
			"数位动态规划": 1,
		},
	})
}

func AtMostNGivenDigitSet(digits []string, n int) int {
	numStr := strconv.Itoa(n)
	//从左往右,避免前导0带来的重复
	//less[i]表示从左往右前0...i位组成的数小于n前0...i位的种类数量（不含等于）
	//equal[i]表示0...i位组成的数是否能组成s对应的位置一样的数
	dp := make([]int, len(numStr))
	equal := make([]bool, len(numStr))
	//第一个位数单独处理
	for j := range digits {
		if digits[j][0] == numStr[0] {
			equal[0] = true
			break
		}

		if digits[j][0] > numStr[0] {
			break
		}

		dp[0]++
	}

	for i := 1; i < len(numStr); i++ {
		//三种来源：
		//前面全是0，新加的一位各种数字都行（因为题目中digits中没有0，所以要考虑这种情况)
		//前面小于s对应的位置，新加的一位各种数字都行
		dp[i] = dp[i-1]*len(digits) + len(digits)
		//前面存在等于s对应的位置，新加的一位要小于s对应的位置
		if equal[i-1] {
			lessCount := 0
			for j := range digits {
				if digits[j][0] == numStr[i] {
					equal[i] = equal[i-1]
					break
				}

				if digits[j][0] > numStr[i] {
					break
				}

				lessCount++
			}
			dp[i] += lessCount
		}
	}

	//如果整体能组成一样的数，+1
	if equal[len(numStr)-1] {
		return dp[len(numStr)-1] + 1
	} else {
		return dp[len(numStr)-1]
	}
}
